import java.util.Arrays;

public class HashBuck {
      //尝试实现哈希桶
     static class Node{
         //设置key值
         public int key;
         //设置val值
         public int val;
         public Node next;  //指向下一个节点的指针

         //赋值的构造方法
         public Node(int key,int val){
              this.key = key;
              this.val = val;
         }
     }

     private Node[] array  = new Node[10];
     private int usedsize = 0;
     private  static  final   double  LoadFACTOR = 0.75;
    //插入数据——key与相应的val
    public void put(int key,int val){
         //在插入数据时，我们先判断此数据在数组中应放在什么位置。
        int index = key%array.length;
        //然后遍历此位置的链表，如果链表中没有此节点，则插入，有则更新value值.
        Node cur = array[index];
        while (cur !=null){
            if(cur.key == key){
                  //说明此key值存在。
                  cur.val = val;
                  return;
            }
            cur = cur.next;
        }
         //当cur为空时，说明插入的key值在链表中并不存在,则进行头插
         cur = new Node(key,val);
        cur.next = array[index];
        array[index] = cur;
        usedsize++;
        //之后再判断当前数组负载因子是否已经过大
        if(isoverload(array,LoadFACTOR)){
             //如果负载因子超过设定的值，则重新开辟一个数组，并进行后续步骤
             resize();
        }
    }
    private void resize() {
         Node []newarray = new Node[2*array.length];
        //应该遍历所有的链表的节点，重新分配到新的位置上去
        for (int i = 0; i < array.length; i++) {
             Node cur = array[i];
            while (cur!=null){
                    int index  =   cur.key % newarray.length;
                    //在重新获取当前的节点应在的下标后
                   // 将此节点插入到应在的下标处
                  Node curN = cur.next;
                   cur.next = newarray[index];
                   newarray[index] =cur;
                   //cur需要回到原来节点的next节点处
                   cur = curN;
            }
        }
        array = newarray;
    }
    private boolean isoverload(Node[] array, double loadfactor) {
        return usedsize%array.length>= loadfactor;
    }


    //获取数据——获取key相应的val值
    public int getVal(int key){
         //判断key值是否存在
         int index = key% array.length;
         Node cur = array[index];
         while (cur!=null){
             if(cur.key==key){
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;
    }































}
